package q76;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个字符串 s 、一个字符串 t 。
 * 返回 s 中涵盖 t 所有字符的最小子串。
 * 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 */
public class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.isEmpty() || t.isEmpty() || t.length() > s.length()) {
            return "";
        }

        Map<Character, Integer> tmap = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            if (tmap.containsKey(t.charAt(i))) {
                tmap.put(t.charAt(i), tmap.get(t.charAt(i)) + 1);
            } else {
                tmap.put(t.charAt(i), 1);
            }
        }

        Map<Character, Integer> smap = new HashMap<>();

        String res = "";
        int i = 0, j = 0;
        while (i < s.length()) {
            if (tmap.containsKey(s.charAt(i))) {
                if (smap.containsKey(s.charAt(i))) {
                    smap.put(s.charAt(i), smap.get(s.charAt(i)) + 1);
                } else {
                    smap.put(s.charAt(i), 1);
                }
            }

            if (check(smap, tmap)) {
                while (check(smap, tmap) && i > j) {
                    if (smap.containsKey(s.charAt(j)) && smap.get(s.charAt(j)) >= tmap.get(s.charAt(j))) {
                        smap.put(s.charAt(j), smap.get(s.charAt(j)) - 1);
                    }
                    j += 1;
                }


                if (check(smap, tmap)) {
                    int len = i - j + 1;
                    if (res.isEmpty() || res.length() > len) {
                        res = s.substring(j, i + 1);
                    }
                } else {
                    int len = i - j + 2;
                    if (res.isEmpty() || res.length() > len) {
                        res = s.substring(j - 1, i + 1);
                    }
                }

            }

            i += 1;
        }

        return res;
    }

    public Boolean check(Map<Character, Integer> smap, Map<Character, Integer> tmap) {
        for(Character t : tmap.keySet()) {
           if (!smap.containsKey(t) || smap.get(t) < tmap.get(t)) {
               return false;
           }
        }
        return true;
    }

    public static void main(String[] args) {
//        String s = "ADOBECODEBANC", t = "ABC";
        String s = "ab", t = "b";
        Solution solution = new Solution();
        System.out.println(solution.minWindow(s, t));
    }
}
